{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost to Change the Final Value of Expression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #math #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数学 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperationsToFlip"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #反转表达式值的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>有效的</strong> 布尔表达式，用字符串 <code>expression</code> 表示。这个字符串包含字符 <code>'1'</code>，<code>'0'</code>，<code>'&amp;'</code>（按位 <strong>与</strong> 运算），<code>'|'</code>（按位 <strong>或</strong> 运算），<code>'('</code> 和 <code>')'</code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>\"()1|1\"</code> 和 <code>\"(1)&amp;()\"</code> <strong>不是有效</strong> 布尔表达式。而 <code>\"1\"</code>， <code>\"(((1))|(0))\"</code> 和 <code>\"1|(0&amp;(1))\"</code> 是 <strong>有效</strong> 布尔表达式。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你的目标是将布尔表达式的 <strong>值</strong> <strong>反转 </strong>（也就是将 <code>0</code> 变为 <code>1</code> ，或者将 <code>1</code> 变为 <code>0</code>），请你返回达成目标需要的 <strong>最少操作</strong> 次数。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，如果表达式 <code>expression = \"1|1|(0&amp;0)&amp;1\"</code> ，它的 <strong>值</strong> 为 <code>1|1|(0&amp;0)&amp;1 = 1|1|0&amp;1 = 1|0&amp;1 = 1&amp;1 = 1</code> 。我们想要执行操作将 <strong>新的</strong> 表达式的值变成 <code>0</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>可执行的 <strong>操作</strong> 如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>将一个 <code>'1'</code> 变成一个 <code>'0'</code> 。</li>\n",
    "\t<li>将一个 <code>'0'</code> 变成一个 <code>'1'</code> 。</li>\n",
    "\t<li>将一个 <code>'&amp;'</code> 变成一个 <code>'|'</code> 。</li>\n",
    "\t<li>将一个 <code>'|'</code> 变成一个 <code>'&amp;'</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意：</strong><code>'&amp;'</code> 的 <strong>运算优先级</strong> 与 <code>'|'</code> <strong>相同</strong> 。计算表达式时，括号优先级 <strong>最高</strong> ，然后按照 <strong>从左到右</strong> 的顺序运算。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>expression = \"1&amp;(0|1)\"\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>我们可以将 \"1&amp;(0<strong>|</strong>1)\" 变成 \"1&amp;(0<strong>&amp;</strong>1)\" ，执行的操作为将一个 '|' 变成一个 '&amp;' ，执行了 1 次操作。\n",
    "新表达式的值为 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>expression = \"(0&amp;0)&amp;(0&amp;0&amp;0)\"\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>我们可以将 \"(0<strong>&amp;0</strong>)<strong>&amp;</strong>(0&amp;0&amp;0)\" 变成 \"(0<strong>|1</strong>)<strong>|</strong>(0&amp;0&amp;0)\" ，执行了 3 次操作。\n",
    "新表达式的值为 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>expression = \"(0|(1|0&amp;1))\"\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>我们可以将 \"(0|(<strong>1</strong>|0&amp;1))\" 变成 \"(0|(<strong>0</strong>|0&amp;1))\" ，执行了 1 次操作。\n",
    "新表达式的值为 0 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= expression.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>expression</code> 只包含 <code>'1'</code>，<code>'0'</code>，<code>'&amp;'</code>，<code>'|'</code>，<code>'('</code> 和 <code>')'</code></li>\n",
    "\t<li>所有括号都有与之匹配的对应括号。</li>\n",
    "\t<li>不会有空的括号（也就是说 <code>\"()\"</code> 不是 <code>expression</code> 的子字符串）。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-to-change-the-final-value-of-expression](https://leetcode.cn/problems/minimum-cost-to-change-the-final-value-of-expression/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-to-change-the-final-value-of-expression](https://leetcode.cn/problems/minimum-cost-to-change-the-final-value-of-expression/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1&(0|1)\"', '\"(0&0)&(0&0&0)\"', '\"(0|(1|0&1))\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        stack_num = []\n",
    "        stack_ops = []\n",
    "\n",
    "        def op_and(x1,y1,x2,y2):\n",
    "            return min(x1+y2,x2+y1,x1+x2), y1+y2\n",
    "        def op_or(x1,y1,x2,y2):\n",
    "            return x1+x2, min(x1+y2,x2+y1,y1+y2)\n",
    "        \n",
    "        def calc():\n",
    "            if len(stack_num)>=2 and stack_ops[-1] in [\"|\", \"&\"]:\n",
    "                x1, y1 = stack_num.pop()\n",
    "                x2, y2 = stack_num.pop()\n",
    "                x_and, y_and = op_and(x1,y1,x2,y2)\n",
    "                x_or, y_or = op_or(x1,y1,x2,y2)\n",
    "                op = stack_ops.pop()\n",
    "                if op=='&':\n",
    "                    stack_num.append((min(x_and,x_or+1),min(y_and,y_or+1)))\n",
    "                else:\n",
    "                    stack_num.append((min(x_or,x_and+1),min(y_or,y_and+1)))\n",
    "\n",
    "        for ch in expression:\n",
    "            if ch in ['(',\"|\",\"&\"]:\n",
    "                stack_ops.append(ch)\n",
    "            elif ch==\")\":\n",
    "                stack_ops.pop()\n",
    "                calc()\n",
    "            else:\n",
    "                if ch ==\"1\":\n",
    "                    stack_num.append((1,0))\n",
    "                    calc()\n",
    "                elif ch ==\"0\":\n",
    "                    stack_num.append((0,1))\n",
    "                    calc()\n",
    "        return max(stack_num[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        states = []\n",
    "        ops = []\n",
    "                \n",
    "        for c in expression:\n",
    "            if c in '01)':\n",
    "                if c == '0':\n",
    "                    states.append((0, 1))\n",
    "                elif c == '1':\n",
    "                    states.append((1, 0))\n",
    "                else:\n",
    "                    assert(ops[-1] == '(')\n",
    "                    ops.pop()\n",
    "                    \n",
    "                if len(ops) > 0 and ops[-1] != '(':\n",
    "                    op = ops.pop()\n",
    "                    p2, q2 = states.pop()\n",
    "                    p1, q1 = states.pop()\n",
    "                    if op == '&':\n",
    "                        states.append((min(p1, p2), min(q1 + q2, 1 + min(q1, q2))))\n",
    "                    else:\n",
    "                        states.append((min(p1 + p2, 1 + min(p1, p2)), min(q1, q2)))\n",
    "            else:\n",
    "                ops.append(c)\n",
    "        \n",
    "        return max(states[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        # 数字栈\n",
    "        stack_num = list()\n",
    "        # 符号栈\n",
    "        stack_op = list()\n",
    "\n",
    "        def op_and(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return min(x1 + x2, x1 + y2, y1 + x2), y1 + y2\n",
    "\n",
    "        def op_or(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return x1 + x2, min(x1 + y2, y1 + x2, y1 + y2)\n",
    "        \n",
    "        # 尝试将数字栈顶的两个二元组和符号栈顶的运算符进行运算\n",
    "        def calc():\n",
    "            if len(stack_num) >= 2 and stack_op[-1] in [\"|\", \"&\"]:\n",
    "                x1, y1 = stack_num.pop()\n",
    "                x2, y2 = stack_num.pop()\n",
    "                \n",
    "                x_and, y_and = op_and(x1, y1, x2, y2)\n",
    "                x_or, y_or = op_or(x1, y1, x2, y2)\n",
    "\n",
    "                if (op := stack_op.pop()) == \"&\":\n",
    "                    stack_num.append((min(x_and, x_or + 1), min(y_and, y_or + 1)))\n",
    "                else:\n",
    "                    stack_num.append((min(x_or, x_and + 1), min(y_or, y_and + 1)))\n",
    "\n",
    "        for ch in expression:\n",
    "            if ch in [\"(\", \"|\", \"&\"]:\n",
    "                stack_op.append(ch)\n",
    "            elif ch == \"0\":\n",
    "                stack_num.append((0, 1))\n",
    "                calc()\n",
    "            elif ch == \"1\":\n",
    "                stack_num.append((1, 0))\n",
    "                calc()\n",
    "            else:\n",
    "                assert ch == \")\"\n",
    "                # 此时符号栈栈顶一定是左括号\n",
    "                stack_op.pop()\n",
    "                calc()\n",
    "\n",
    "        return max(stack_num[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        nums = []\n",
    "        ops = []\n",
    "\n",
    "        def op_and(x1, y1, x2, y2):\n",
    "            x = min(x1 + x2, x1 + y2, x2 + y1)\n",
    "            y = y1 + y2\n",
    "\n",
    "            return x, y\n",
    "\n",
    "        def op_or(x1, y1, x2, y2):\n",
    "            x = x1 + x2\n",
    "            y = min(y1 + y2, x1 + y2, x2 + y1)\n",
    "\n",
    "            return x, y\n",
    "\n",
    "        def calc():\n",
    "            x1, y1 = nums.pop()\n",
    "            x2, y2 = nums.pop()\n",
    "            op = ops.pop()\n",
    "\n",
    "            x_and, y_and = op_and(x1, y1, x2, y2)\n",
    "            x_or, y_or = op_or(x1, y1, x2, y2)\n",
    "\n",
    "            if op == '&':\n",
    "                nums.append((min(x_and, x_or + 1), min(y_and, y_or + 1)))\n",
    "            else:\n",
    "                nums.append((min(x_and + 1, x_or), min(y_and + 1, y_or)))\n",
    "\n",
    "        for i, t in enumerate(expression):\n",
    "            if t == '(':\n",
    "                ops.append('(')\n",
    "            elif t == ')':\n",
    "                while ops and ops[-1] != '(':\n",
    "                    calc()\n",
    "\n",
    "                if ops and ops[-1] == '(':\n",
    "                    ops.pop()\n",
    "\n",
    "            elif t in ('0', '1'):\n",
    "                if t == '0':\n",
    "                    nums.append((0, 1))\n",
    "                else:\n",
    "                    nums.append((1, 0))\n",
    "\n",
    "            else:\n",
    "                while ops and ops[-1] != '(':\n",
    "                    calc()\n",
    "                \n",
    "                ops.append(t)\n",
    "\n",
    "        while ops:\n",
    "            calc()\n",
    "\n",
    "        return max(nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        states = []\n",
    "        ops = []\n",
    "                \n",
    "        for c in expression:\n",
    "            if c in '01)':\n",
    "                if c == '0':\n",
    "                    states.append((0, 1))\n",
    "                elif c == '1':\n",
    "                    states.append((1, 0))\n",
    "                else:\n",
    "                    assert(ops[-1] == '(')\n",
    "                    ops.pop()\n",
    "                    \n",
    "                if len(ops) > 0 and ops[-1] != '(':\n",
    "                    op = ops.pop()\n",
    "                    p2, q2 = states.pop()\n",
    "                    p1, q1 = states.pop()\n",
    "                    if op == '&':\n",
    "                        states.append((min(p1, p2), min(q1 + q2, 1 + min(q1, q2))))\n",
    "                    else:\n",
    "                        states.append((min(p1 + p2, 1 + min(p1, p2)), min(q1, q2)))\n",
    "            else:\n",
    "                ops.append(c)\n",
    "        \n",
    "        return max(states[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "\n",
    "\n",
    "        stack_num = list()\n",
    "        # 符号栈\n",
    "        stack_op = list()\n",
    "\n",
    "        def op_and(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return min(x1 + x2, x1 + y2, y1 + x2), y1 + y2\n",
    "\n",
    "        def op_or(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return x1 + x2, min(x1 + y2, y1 + x2, y1 + y2)\n",
    "        \n",
    "        # 尝试将数字栈顶的两个二元组和符号栈顶的运算符进行运算\n",
    "        def calc():\n",
    "            if len(stack_num) >= 2 and stack_op[-1] in [\"|\", \"&\"]:\n",
    "                x1, y1 = stack_num.pop()\n",
    "                x2, y2 = stack_num.pop()\n",
    "                \n",
    "                x_and, y_and = op_and(x1, y1, x2, y2)\n",
    "                x_or, y_or = op_or(x1, y1, x2, y2)\n",
    "\n",
    "                if (op := stack_op.pop()) == \"&\":\n",
    "                    stack_num.append((min(x_and, x_or + 1), min(y_and, y_or + 1)))\n",
    "                else:\n",
    "                    stack_num.append((min(x_or, x_and + 1), min(y_or, y_and + 1)))\n",
    "\n",
    "        for ch in expression:\n",
    "            if ch in [\"(\", \"|\", \"&\"]:\n",
    "                stack_op.append(ch)\n",
    "            elif ch == \"0\":\n",
    "                stack_num.append((0, 1))\n",
    "                calc()\n",
    "            elif ch == \"1\":\n",
    "                stack_num.append((1, 0))\n",
    "                calc()\n",
    "            else:\n",
    "                assert ch == \")\"\n",
    "                # 此时符号栈栈顶一定是左括号\n",
    "                stack_op.pop()\n",
    "                calc()\n",
    "\n",
    "        return max(stack_num[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        stack_num = list()\n",
    "        # 符号栈\n",
    "        stack_op = list()\n",
    "\n",
    "        def op_and(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return min(x1 + x2, x1 + y2, y1 + x2), y1 + y2\n",
    "\n",
    "        def op_or(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return x1 + x2, min(x1 + y2, y1 + x2, y1 + y2)\n",
    "        \n",
    "        # 尝试将数字栈顶的两个二元组和符号栈顶的运算符进行运算\n",
    "        def calc():\n",
    "            if len(stack_num) >= 2 and stack_op[-1] in [\"|\", \"&\"]:\n",
    "                x1, y1 = stack_num.pop()\n",
    "                x2, y2 = stack_num.pop()\n",
    "                \n",
    "                x_and, y_and = op_and(x1, y1, x2, y2)\n",
    "                x_or, y_or = op_or(x1, y1, x2, y2)\n",
    "\n",
    "                if (op := stack_op.pop()) == \"&\":\n",
    "                    stack_num.append((min(x_and, x_or + 1), min(y_and, y_or + 1)))\n",
    "                else:\n",
    "                    stack_num.append((min(x_or, x_and + 1), min(y_or, y_and + 1)))\n",
    "\n",
    "        for ch in expression:\n",
    "            if ch in [\"(\", \"|\", \"&\"]:\n",
    "                stack_op.append(ch)\n",
    "            elif ch == \"0\":\n",
    "                stack_num.append((0, 1))\n",
    "                calc()\n",
    "            elif ch == \"1\":\n",
    "                stack_num.append((1, 0))\n",
    "                calc()\n",
    "            else:\n",
    "                assert ch == \")\"\n",
    "                # 此时符号栈栈顶一定是左括号\n",
    "                stack_op.pop()\n",
    "                calc()\n",
    "\n",
    "        return max(stack_num[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "\n",
    "        stack_num = list()\n",
    "        stack_op = list()\n",
    "\n",
    "        def op_and(x1, y1, x2,y2):\n",
    "            return min(x1+x2, x1+y2,y1+x2), y1+y2 \n",
    "        \n",
    "        def op_or(x1, y1,x2,y2):\n",
    "            return x1+x2, min(y1+y2, y1+x2, x1+y2)\n",
    "        \n",
    "        def calc():\n",
    "            if len(stack_num)>=2 and stack_op[-1] in [\"|\", \"&\"]:\n",
    "                x1,y1 = stack_num.pop()\n",
    "                x2,y2 = stack_num.pop()\n",
    "\n",
    "                x_and, y_and = op_and(x1,y1, x2,y2)\n",
    "                x_or, y_or = op_or(x1,y1,x2,y2)\n",
    "\n",
    "                opx = stack_op.pop()\n",
    "                if opx==\"&\":\n",
    "                    x_and, y_and = min(x_and, x_or+1), min(y_and,y_or+1)\n",
    "                    stack_num.append((x_and,y_and))\n",
    "                \n",
    "                elif opx==\"|\":\n",
    "                    x_or, y_or = min(x_or, x_and+1), min(y_or, y_and+1)\n",
    "                    stack_num.append((x_or,y_or))\n",
    "        \n",
    "        for ch in expression:\n",
    "            if ch in [\"(\", \"|\", \"&\"]:\n",
    "                stack_op.append(ch)\n",
    "            elif ch==\"0\":\n",
    "                stack_num.append( (0,1) )\n",
    "                calc()\n",
    "            elif ch==\"1\":\n",
    "                stack_num.append((1,0))\n",
    "                calc()\n",
    "            else:\n",
    "                assert ch==\")\"\n",
    "                stack_op.pop()\n",
    "                calc()\n",
    "        return max(stack_num[0])\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
